
package com.huawei.common.okhttp;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_23_合并K个升序链表 {
    public static void main(String args[]) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(5)));
        ListNode listNode2 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode listNode3 = new ListNode(2, new ListNode(3, new ListNode(4)));
        ListNode[] lists = new ListNode[]{listNode1, listNode2, listNode3};
        ListNode[] lists1 = new ListNode[]{listNode1, listNode2, listNode3};
        // 方法1
//        ListNode retListNode = mergeKLists(lists);
        // 方法2
        ListNode retListNode1 = mergeKLists2(lists1);

//        System.out.println(retListNode);
        System.out.println(retListNode1);
    }
    public static ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return new ListNode();
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode tempListNode = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ListNode curentListNode = lists[i];
            tempListNode = mergeTwoListNode2(tempListNode, curentListNode);
        }
        return tempListNode;
    }
    public static ListNode mergeTwoListNode2(ListNode listNodeA, ListNode listNodeB) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        ListNode nodeA = listNodeA;
        ListNode nodeB = listNodeB;
        while (nodeA != null && nodeB != null) {
            if (nodeA.val < nodeB.val) {
                tail.next = nodeA;
                nodeA = nodeA.next;
            } else {
                tail.next = nodeB;
                nodeB = nodeB.next;
            }
            tail = tail.next;
        }
        tail.next = nodeA == null ? nodeB : nodeA;
        return head.next;
    }
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return new ListNode();
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode tempListNode = lists[0];

        for (int i = 1; i < lists.length; i++) {
            ListNode curentListNode = lists[i];
            tempListNode = mergeTwoListNode(tempListNode, curentListNode);
        }
        return tempListNode;
    }

    public static ListNode mergeTwoListNode(ListNode listNode, ListNode listNodeOther) {
        if (listNode == null && listNodeOther == null) {
            return null;
        }
        if (listNode == null) {
            return listNodeOther;
        }
        if (listNodeOther == null) {
            return listNode;
        }
        int val = listNode.val;
        int otherVal = listNodeOther.val;
        ListNode midNode = null;
        ListNode temNextNode;
        // 调换位置
        if (val > otherVal) {
            temNextNode = listNodeOther;
            listNodeOther = listNode;
            listNode = temNextNode;
        }
        ListNode currenNode = listNode;
        do {
            int currentVal = currenNode.val;
            if (otherVal < currentVal) {
                break;
            }
            ListNode nextNode = currenNode.next;
            if (nextNode != null) {
                if (otherVal < nextNode.val) {
                    currenNode.next = listNodeOther;
                    midNode = nextNode;
                    break;
                }
                currenNode = currenNode.next;
            } else {
                currenNode.next = listNodeOther;
                break;
            }
        } while (true);
        return mergeTwoListNode(listNode, midNode);
    }

}